﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphTheory.Task1
{
    class GraphForPrim
    {
        public int[] Vertices { get; private set; }
        public int[,] AdjacencyMatrix { get; private set; }
        public int[,] WeightMatrix { get; private set; }
        private int max;

        public GraphForPrim(int[] Vertices, int[,] AdjacencyMatrix, int[,] WeightMatrix)
        {
            this.Vertices = Vertices;
            this.AdjacencyMatrix = AdjacencyMatrix;
            this.WeightMatrix = WeightMatrix;

            int max = 0;
            for (int i = 0; i < Vertices.Length; i++)
            {
                for (int j = 0; j < Vertices.Length; j++)
                {
                    if (AdjacencyMatrix[i, j] == 1)
                    {
                        max += Math.Abs(WeightMatrix[i,j]);
                    }
                }
            }
            this.max = max;
        }

        public GraphForPrim(int VerticesAmount, int[,] AdjacencyMatrix, int[,] WeightMatrix)
        {
            this.Vertices = new int[VerticesAmount];
            for (int i = 0; i < VerticesAmount; i++)
            {
                this.Vertices[i] = i;
            }
            this.AdjacencyMatrix = AdjacencyMatrix;
            this.WeightMatrix = WeightMatrix;
            int max = 0;
            for (int i = 0; i < Vertices.Length; i++)
            {
                for (int j = 0; j < Vertices.Length; j++)
                {
                    if (AdjacencyMatrix[i, j] == 1)
                    {
                        max += Math.Abs(WeightMatrix[i, j]);
                    }
                }
            }
            this.max = max;
        }

        public static GraphForPrim ParseFromString(string str)
        {
            StringScanner scanner = new StringScanner(str);
            int VerticesAmount = scanner.nextInt();
            int[,] AdjacencyMatrix = new int[VerticesAmount, VerticesAmount];
            int[,] WeightMatrix = new int[VerticesAmount, VerticesAmount];

            for (int i = 0; i < VerticesAmount; i++)
            {
                for (int j = 0; j < VerticesAmount; j++)
                {
                    AdjacencyMatrix[i, j] = scanner.nextInt();
                }
            }

            for (int i = 0; i < VerticesAmount; i++)
            {
                for (int j = 0; j < VerticesAmount; j++)
                {
                    WeightMatrix[i, j] = scanner.nextInt();
                }
            }

            return new GraphForPrim(VerticesAmount, AdjacencyMatrix, WeightMatrix);
        }

        public PureGraph GetMinimumSpanningTree()
        {
            List<int> TreeVertices = new List<int>();
            List<int> OtherVertices = this.Vertices.ToList();
            List<Tuple<int, int>> TreeEdges = new List<Tuple<int, int>>();

            if (OtherVertices == null || OtherVertices.Count == 0)
            {
            }
            else
            {

                int nextVertice = OtherVertices.First();
                OtherVertices.Remove(nextVertice);
                TreeVertices.Add(nextVertice);
                while (OtherVertices.Count != 0)
                {
                    Tuple<int, int> MinimumEdge = GetMinimumEdgeBetween(TreeVertices, OtherVertices);
                    OtherVertices.Remove(MinimumEdge.Item2);
                    TreeVertices.Add(MinimumEdge.Item2);
                    TreeEdges.Add(MinimumEdge);
                }
            }

            int[] TreeVerticesArr = this.Vertices.Clone() as int[];
            int[,] AdjacencyMatrix = new int[TreeVerticesArr.Length, TreeVerticesArr.Length];
            foreach (var edge in TreeEdges)
            {
                int index1 = GetIndex(TreeVerticesArr, edge.Item1);
                int index2 = GetIndex(TreeVerticesArr, edge.Item2);
                AdjacencyMatrix[index1, index2] = 1;
                AdjacencyMatrix[index2, index1] = 1;
            }
            return new PureGraph(TreeVerticesArr, AdjacencyMatrix);
        }


        private Tuple<int, int> GetMinimumEdgeBetween(List<int> Component1, List<int> Component2)
        {
            int min = this.max;
            Tuple<int, int> MinimumEdge = null;

            foreach (var vertex1 in Component1)
            {
                int index1 = GetIndex(this.Vertices, vertex1);
                foreach (var vertex2 in Component2)
                {
                    int index2 = GetIndex(this.Vertices, vertex2);
                    if (this.AdjacencyMatrix[index1, index2] == 1 && this.WeightMatrix[index1, index2] <= min)
                    {
                        MinimumEdge = new Tuple<int, int>(vertex1, vertex2);
                        min = this.WeightMatrix[index1, index2];
                    }

                }
            }
            return MinimumEdge;

        }

        private static int GetIndex(int[] Vertices, int vrt)
        {
            for (int i = 0; i < Vertices.Length; i++)
            {
                if (Vertices[i] == vrt)
                {
                    return i;
                }
            }
            throw new ArgumentException();
        }

        public int computeLength(int[] path)
        {
            int res = 0;
            for (int i = 0; i < path.Length - 1; i++)
            {

                res += this.GetArcWeight(path[i], path[i + 1]);
            }
            return res;
        }

        public static List<int> GetOutgoingVertices(GraphForPrim digraph, int vertex)
        {
            int index = GetIndex(digraph.Vertices, vertex);
            List<int> res = new List<int>();
            for (int j = 0; j < digraph.Vertices.Length; j++)
            {
                if (digraph.AdjacencyMatrix[index, j] == 1)
                {
                    res.Add(digraph.Vertices[j]);
                }
            }

            return res;
        }

        public void AddArc(int source, int sink, int weight)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            this.AdjacencyMatrix[indexSource, indexSink] = 1;
            this.WeightMatrix[indexSource, indexSink] = weight;
        }

        public Tuple<int, int, int> DeleteArc(int source, int sink)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            this.AdjacencyMatrix[indexSource, indexSink] = 0;
            int weight = this.WeightMatrix[indexSource, indexSink];
            this.WeightMatrix[indexSource, indexSink] = 0;
            return new Tuple<int,int,int>(source, sink, weight);
        }

        public int GetArcWeight(int source, int sink)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            return this.WeightMatrix[indexSource, indexSink];
        }
    }
}
